// https://leetcode.cn/problems/trapping-rain-water/
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;


class Solution {
public:
    // 思路：
    /*
     * 三指针思路： l, m ,r
     * 如果m >= l 说明当前mid不符合条件，l++; m++;r++;
     * while m + 1 <= m; m++;r++;
     * while r + 1 > r; r++;
     * else 计算雨水
     * l = r; m = l+1
     * */
    // 0 1 0 2 1 0 1 3 2 1 2 1
    int trap(vector<int> &height) {
        int sum = 0;
        while (1) {
            int num = t(height);
            sum += num;
            if (num == 0) break;
        }
        return sum;
    }

    int t(vector<int> &height) {
        int len = height.size();
        if (len < 3) return 0;
        int l = 0, m = 1, r = 2;
        int sum = 0;
        while (r < len) {
            while (height[m] >= height[l]) {
                l++;
                m++;
                r++;
                if (r >= len) {
                    return sum;
                }
            }
            while (m < len - 1 && height[m + 1] <= height[m]) {
                m++;
                r++;
                if (r >= len) {
                    return sum;
                }
            }
            while (r < len - 1 && height[r + 1] > height[r]) {
                r++;
            }

            if (height[r] > height[m]) {
                sum += calc(height, l, m, r);
                l = r;
                m = l + 1;
                r = m + 1;
            }
        }
        return sum;
    }

    int calc(vector<int> &height, int l, int m, int r) {
        int sum = 0;
        int minH = min(height[l], height[r]);
        while (l < r) {
            if (height[l] < minH) {
                sum += minH - height[l];
                height[l] = minH;
            }
            l++;
        }
        return sum;
    }
};

int main() {
    Solution so;
    vector<int> height{6, 4, 2, 0, 3, 2, 0, 3, 1, 4, 5, 3, 2, 7, 5, 3, 0, 1, 2, 1, 3, 4, 6, 8, 1, 3};//
    int index = so.trap(height);
    cout << index << endl;
    return 0;
}